package cn.bellychang.bobo.sort;

import java.util.Random;

/**
 * @author ChangLiang
 * @date 2021/2/1
 */
public class SortUtil2 {

    private static final Random RANDOM = new Random();

    enum SortAlgorithm {
        /**
         *
         */
        quickSort
    }

    enum PartitionAlgorithm {
        /**
         * 选取第一个值作为pivot
         */
        partition01,
        /**
         * 采用随机index作为pivot
         */
        partition02,
        /**
         * 双路快排
         */
        partition03,
        /**
         * 三路快排
         */
        partition04
    }

    public static <E extends Comparable<E>> E[] sort(String sortAlgorithmName, String partitionAlgorithmName, E[] arr) {
        if (sortAlgorithmName.equals(SortAlgorithm.quickSort.name())) {
            return quickSort(partitionAlgorithmName, arr);
        } else {
            throw new RuntimeException(sortAlgorithmName + " is not supported now");
        }
    }

    private static <E extends Comparable<E>> E[] quickSort(String partitionAlgorithmName, E[] arr) {
        if (arr.length > 1) {
            quickSort(partitionAlgorithmName, 0, arr.length - 1, arr);
        }
        return arr;
    }

    private static <E extends Comparable<E>> void quickSort(String partitionAlgorithmName, int beginIndex, int endIndex, E[] arr) {
        if (beginIndex >= endIndex) {
            return;
        }
        if (partitionAlgorithmName.equals(PartitionAlgorithm.partition01.name())) {
            int pivotIndex = partition01(beginIndex, endIndex, arr);
            quickSort(partitionAlgorithmName, beginIndex, pivotIndex - 1, arr);
            quickSort(partitionAlgorithmName, pivotIndex + 1, endIndex, arr);
        } else if (partitionAlgorithmName.equals(PartitionAlgorithm.partition02.name())) {
            int pivotIndex = partition02(beginIndex, endIndex, arr);
            quickSort(partitionAlgorithmName, beginIndex, pivotIndex - 1, arr);
            quickSort(partitionAlgorithmName, pivotIndex + 1, endIndex, arr);
        } else if (partitionAlgorithmName.equals(PartitionAlgorithm.partition03.name())) {
            int pivotIndex = partition03(beginIndex, endIndex, arr);
            quickSort(partitionAlgorithmName, beginIndex, pivotIndex - 1, arr);
            quickSort(partitionAlgorithmName, pivotIndex + 1, endIndex, arr);
        } else if (partitionAlgorithmName.equals(PartitionAlgorithm.partition04.name())) {
            IndexPair indexPair = partition04(beginIndex, endIndex, arr);
            quickSort(partitionAlgorithmName, beginIndex, indexPair.getLt() - 1, arr);
            quickSort(partitionAlgorithmName, indexPair.getGt() + 1, endIndex, arr);
        }
    }

    public static <E extends Comparable<E>> IndexPair partition04(int beginIndex, int endIndex, E[] arr) {
        E pivot = arr[beginIndex];
        int lt = beginIndex + 1;
        int gt = endIndex;
        int i = beginIndex + 1;

        // loop invariant: [beginIndex...lt-1]<v [lt...i-1]=v  [gt+1, endIndex]>v
        while (i < gt + 1) {
            // 扩充 <v 部分
            if (arr[i].compareTo(pivot) < 0) {
                if (lt != i) {
                    swap(lt, i, arr);
                }
                lt++;
                i++;
            } else if (arr[i].compareTo(pivot) > 0) {
                // 扩充 >v 部分
                swap(gt, i, arr);
                gt--;
                // 注意：此时i不要++ 因为新换来一个元素
            } else {
                // 扩充 =v 部分
                i++;
            }
        }
        // 这里swap是i-1 要考虑相等的情况
        swap(beginIndex, lt - 1, arr);
        // 返回的时候 返回的是pivotIndex 其还需要-1 和 +1
        return new IndexPair(lt - 1, gt);
    }


    public static <E extends Comparable<E>> int partition03(int beginIndex, int endIndex, E[] arr) {
        // 关键在于对于等于这个标定点pivot的元素，我们要将其平分到标定点的两端
        E pivot = arr[beginIndex];
        int i = beginIndex + 1;
        int j = endIndex;

        // 写这段代码可以考虑两种情况
        // 1,2,3,4  j=0
        // 4,3,2,1  j=3
        while (true) {
            while (i <= j && arr[i].compareTo(pivot) < 0) {
                i++;
            }
            while (j >= i && arr[j].compareTo(pivot) > 0) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(i, j, arr);
            // 要i++ j++ 否则可能出现i->4 j->4 无限循环的情况
            i++;
            j--;
        }
        swap(beginIndex, j, arr);
        return j;
    }

    public static <E extends Comparable<E>> int partition02(int beginIndex, int endIndex, E[] arr) {
        int l = RANDOM.nextInt(endIndex - beginIndex + 1) + beginIndex;
        E pivot = arr[l];
        System.out.println("pivot = " + pivot);
        swap(beginIndex, l, arr);

        int j = beginIndex + 1;
        int i = beginIndex + 1;
        // loop invariant:
        while (i <= endIndex) {
            if (arr[i].compareTo(pivot) < 0) {
                swap(j, i, arr);
                j++;
            }
            i++;
        }
        swap(beginIndex, j - 1, arr);
        return j - 1;

    }

    public static <E extends Comparable<E>> int partition01(int beginIndex, int endIndex, E[] arr) {
        // take the first value in array
        E pivot = arr[beginIndex];
        int j = beginIndex + 1;
        int i = beginIndex + 1;
        // loop invariant:
        while (i <= endIndex) {
            if (arr[i].compareTo(pivot) < 0) {
                swap(j, i, arr);
                j++;
            }
            i++;
        }
        swap(beginIndex, j - 1, arr);
        return j - 1;
    }

    private static <E> void swap(int fromIndex, int toIndex, E[] arr) {
        E temp = arr[fromIndex];
        arr[fromIndex] = arr[toIndex];
        arr[toIndex] = temp;
    }
}

class IndexPair {
    private int lt;
    private int gt;

    public IndexPair(int lt, int gt) {
        this.lt = lt;
        this.gt = gt;
    }

    public int getLt() {
        return lt;
    }

    public int getGt() {
        return gt;
    }
}
